package com.xiaoyu.sort.basic;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 基数排序
 * @author: YuWenYi
 * @create: 2021-04-30 11:06
 **/
public class RadixSort {

    //简单来说,先根据个位数进行排序,然后再根据十位数进行排序,再根据百位数进行排序,以此类推,时间复杂度很低
    //如果使用二维数组作为桶,那么空间复杂度很高,如果你测试数据达到8000W,将会出现Out of Memory(OOM)
    public static void radixSort(int[] arr){
        //获取数组中的最大的数字的位数
        int max = arr[0];
        for (int a : arr) {
            if (a > max) {
                max = a;
            }
        }
        int maxDigit = String.valueOf(max).length();

        //定义10个桶,即0-9的长度
        //由于每个桶并不能确定有多个个数据会放入,所以只能采取最笨的方式,每个桶的长度都是arr.length
        //其实这里更好的做法应该是使用邻接表,才能不这么浪费空间
        int[][] buckets = new int[10][arr.length];
        //用它来记录每个桶中的数据是多少个
        //例如everyBucketCount[0]的数字,就是等于buckets[0]中元素的个数
        int[] everyBucketCount = new int[10];

        //循环最大数字的位数次
        for (int d = 0; d < maxDigit; d++) {
            //以个位,十位,百位这样的顺序,来将数字放入桶中又取出,只需要最大的数字的"位数"次循环,就能将所有数字排序
            //取个位: num / 1 % 10;  取十位: num / 10 % 10;  取百位num / 100 % 10以此类推
            for (int i = 0; i < arr.length; i++) {
                int digit = arr[i] / (int)Math.pow(10,d) % 10;
                buckets[digit][everyBucketCount[digit]] = arr[i];
                everyBucketCount[digit]++;
            }
            //再把入桶的数取出,即依次遍历10个桶,把每个桶的元素全部取出放到arr中
            int index = 0;
            for (int bucketNum = 0;bucketNum < 10; bucketNum ++){
                if (everyBucketCount[bucketNum] != 0) {   //遍历0-9号桶
                    //然后将该桶中的元素依次放回arr中
                    for (int count = 0; count < everyBucketCount[bucketNum]; count++) {
                        //把该桶中的第count个元素,放到arr中,然后让arr的index++
                        arr[index] = buckets[bucketNum][count];
                        index++;
                    }
                    everyBucketCount[bucketNum] = 0;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = new int[]{-9,-2,-17,4,6,-20,9,8,-16,50,4,15};
        int[] nums = new int[]{8,90,1,70,2,3,500,4,60,3};
        radixSort(nums);
        //System.out.println(Arrays.toString(nums));

        //速率测试  800万数据在0.5秒左右.... 但是空间复杂度超级高,,如果使用8000万数据测试则会出现OOM
        int[] bigData = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            bigData[i] = (int)(Math.random() * 8000000);
        }
        long start = System.currentTimeMillis();
        radixSort(bigData);
        long stop = System.currentTimeMillis();

        System.out.println((stop-start)/1000.0);
    }

}
